package leecode.findmiddle;

import java.util.*;

public class Solution {
    // 取每一层的元素，用一个当前队列的长度做二次循环即可
    public List<List<Integer>> levelOrder() {
        List<List<Integer>> res = new ArrayList<>();
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(head);

        while (!queue.isEmpty()) {
            int len = queue.size();

            List<Integer> list = new ArrayList<>();
            while (len > 0) {
                Node node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                len--;
            }
            res.add(list);
        }

        return res;
    }

    public void dieDai() {
        Stack<Node> stack = new Stack<>();
        stack.add(head);
        while (!stack.empty()) {
            Node node = stack.pop();
            System.out.print(node.val + "   ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null)
                stack.push(node.left);

        }
    }

    class Node {
        int val;
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    private Node head;


    List<List<Node>> res = new ArrayList<>();

    public void findAllPath() {
        System.out.println("从上往下数：");
        List<Node> cur = new ArrayList<>();
        findPath(head, cur);
        deal(res);
//        System.out.println(res);

    }

    private void deal(List<List<Node>> res) {
        for (List<Node> list : res) {
            findTheMiddle(list);
        }
    }

    private void findTheMiddle(List<Node> list) {
        int sum = 0;
        int mid = 0;
        for (Node node : list) {
            sum += node.val;
        }
        for (Node node : list) {
            if (mid == (sum - node.val) / 2) {
                System.out.println("第" + (list.indexOf(node) + 1) + "个" + node.val + " 上下两侧的和相等");
            }
            mid += node.val;
        }
        // 寻找中间某个点，两侧的和是否相等
        // 公式，当前和是否等于总和的一半
    }

    private void findPath(Node node, List<Node> cur) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) { // 叶子结点，保存结果并添加到res
            cur.add(node);
            res.add(new ArrayList<>(cur));
            cur.remove(cur.size() - 1);
            return;
        }
        cur.add(node);
        findPath(node.left, cur);
        findPath(node.right, cur);
        cur.remove(cur.size() - 1);
    }

    public void init() {
        head = new Node(7);
        head.left = new Node(6);
        head.left.left = new Node(3);
        head.left.left.left = new Node(11);
        head.left.left.left.left = new Node(2);
        head.right = new Node(5);
        head.right.left = new Node(4);
        head.right.left.left = new Node(1);
        head.right.left.right = new Node(3);
        head.right.left.left.right = new Node(16);
    }
}
